package com.demo.java.OD201_250.OD239;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【核酸检测人员安排 | 总最快检测效率 or 核酸检测效率】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145940078
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);  // 创建Scanner对象，用于输入
        int nC = getInputValue(sc, "");  // 获取“nC”值，表示某种资源或对象的数量
        int nV = getInputValue(sc, "");  // 获取“nV”值，表示可以选择的某种数量或次数

        // 存储每个资源（或对象）的效率
        int[] sEfficiencies = new int[nC];
        for (int i = 0; i < nC; i++) {
            // 获取每个资源的初始效率
            sEfficiencies[i] = getInputValue(sc, (i + 1) + "");
        }

        // 存储每个资源（或对象）的修正效率，这里通过sEfficiencies[i] / 10来简化效率值
        int[] fEfficiencies = new int[nC];
        for (int i = 0; i < nC; i++) {
            fEfficiencies[i] = sEfficiencies[i] / 10;
        }

        // 创建一个二维dp数组，dp[i][j]表示考虑前i个资源时，选择了j个资源的最优值
        int[][] dp = new int[nC + 1][nV + 1];

        // 计数器，用于记录资源的效率变化
        int count = 0;

        // 初始化dp数组的第一列，dp[i][0]表示不选择任何资源时的状态
        for (int i = 1; i < nC + 1; i++) {
            // 计算每个资源在不选择时的效果（当前效率 - 修正后的效率 * 2）
            count += (sEfficiencies[i - 1] - 2 * fEfficiencies[i - 1]);
            dp[i][0] = count;  // 记录每个选择0个资源时的效果
        }

        // 通过动态规划填充dp数组
        for (int i = 1; i < nC + 1; i++) {
            for (int j = 1; j < nV + 1; j++) {
                // 考虑三种情况来更新dp[i][j]的值：
                // 1. 不选择当前资源，只取前i-1个资源的最大值，且效率变化为sEfficiencies[i-1] - 2 * fEfficiencies[i-1]
                dp[i][j] = Math.max(dp[i - 1][j] + sEfficiencies[i - 1] - 2 * fEfficiencies[i - 1],
                        dp[i - 1][j - 1] + sEfficiencies[i - 1]);
                // 2. 选择当前资源时，j-2个资源的最优值，加上当前资源的效率和修正效率
                dp[i][j] = Math.max(dp[i][j],
                        j - 2 >= 0 ? dp[i - 1][j - 2] + sEfficiencies[i - 1] +
                                fEfficiencies[i - 1] :
                                0);
                // 3. 选择当前资源时，j-3个资源的最优值，加上当前资源的效率和修正后的2倍效率
                dp[i][j] = Math.max(dp[i][j],
                        j - 3 >= 0 ? dp[i - 1][j - 3] + sEfficiencies[i - 1] + 2 *
                                fEfficiencies[i - 1] :
                                0);
                // 4. 选择当前资源时，j-4个资源的最优值，加上当前资源的效率和修正后的3倍效率
                dp[i][j] = Math.max(dp[i][j],
                        j - 4 >= 0 ? dp[i - 1][j - 4] + sEfficiencies[i - 1] + 3 *
                                fEfficiencies[i - 1] :
                                0);
            }
        }

        // 最终输出动态规划表中所有资源选择nV个资源时的最优值
        System.out.println(dp[nC][nV]);
    }

    // 辅助方法，用于从Scanner中获取整数输入
    private static int getInputValue(Scanner sc, String message) {
        return sc.nextInt();
    }
}